package 第一章基础算法.快速排序.id785快速排序;

import java.util.Scanner;

/**
 * 输入格式
 * 输入共两行，第一行包含整数 n。
 * 第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
 *
 * 输出格式
 * 输出共一行，包含 n 个整数，表示排好序的数列。
 *
 * 数据范围
 * 1≤n≤100000
 */
class Main{

    public static void main(String[]args){
        //读取输入数组
        Scanner scanner = new Scanner(System.in);
        int len = scanner.nextInt();
        int[] nums = new int[len];
        for(int i = 0;i<len;i++){
            nums[i] = scanner.nextInt();
        }
        //快排
        quickSort(nums,0,len-1);
        //打印结果
        for(int x : nums){
            System.out.print(x + " ");
        }
    }

    public static void quickSort(int[] nums,int l ,int r){
        if(l >= r)return;
        int p1 = l-1;
        int p2 = r+1;
        int pivot = nums[l];
        while(p1 < p2){
            do{p1++;}while(nums[p1] < pivot);
            do{p2--;}while(nums[p2] > pivot);
            if(p1 < p2){
                swap(nums,p1,p2);
            }
        }
        quickSort(nums,l,p2);
        quickSort(nums,p2+1,r);
    }

    public static void swap(int[]nums,int a,int b){
        int x = nums[a];
        nums[a] = nums[b];
        nums[b] = x;
    }

}



